package SearchAlgorithm;

// 二分查找
public class BinarySearch {
    // 循环
    public static int binarySearch(int[] array,int left, int right, int target){

        while(left <= right){
            int mid = (left + right) / 2;
            if(target == array[mid]){// 如果目标值和中位值相等 直接返回mid
                return mid;
            }
            if(target < array[mid]){ // 如果目标值 < 中位值，左指针不变，右指针变为中位指针的前面
                right = mid - 1;
            }

            if(target > array[mid]){
                left = mid + 1;
            }
        }
        return -1;
    }


    // 递归
    public static int binarySearch1(int[] array,int left, int right, int target){
        int mid = (left + right) / 2;
        if(left <= right){
            if(target < array[mid]){ // 如果目标值 < 中位值，左指针不变，右指针变为中位指针的前面
                return binarySearch1(array,left, mid - 1, target);
            }else if(target > array[mid]){
                return binarySearch1(array,mid + 1, right, target);
            }else {
                return mid;
            }
        }else {
            return -1;
        }
    }

    public static void main(String[] args) {
        System.out.println(binarySearch1(new int[]{2,3,4,5,6,7}, 0, 5, 2));
    }
}
